//https://leetcode.cn/problems/maximum-difference-score-in-a-grid/?envType=daily-question&envId=2024-08-15https://leetcode.cn/problems/maximum-difference-score-in-a-grid/?envType=daily-question&envId=2024-08-15

class Solution {
public:
    int maxScore(vector<vector<int>>& grid) {
        int n = grid.size(),m = grid[0].size();
        vector<vector<int>> dp(n,vector<int>(m,-1e9));
        int ans = INT_MIN;
        // 处理外层
        for(int j = 1; j < m; j++){ // 第一层只能从左边一整个来跟从左边一个来取最值
            dp[0][j] = max(dp[0][j - 1] + grid[0][j] - grid[0][j - 1], 
                            grid[0][j] - grid[0][j - 1]);
            ans = max(ans,dp[0][j]);
        }
        for(int i = 1; i < n; i++){ // 第一列只能从上边一整个来跟从上面一个来取最值
            dp[i][0] = max(dp[i - 1][0] + grid[i][0] - grid[i - 1][0], 
                            grid[i][0] - grid[i - 1][0]);
            ans = max(ans,dp[i][0]);
        }
        // 四种情况取最大值
        // 1、左边一整个来
        // 2、由左边一个来
        // 3、上边一整个来
        // 4、由上边一个来
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){ 
                dp[i][j] = max({dp[i - 1][j] + grid[i][j] - grid[i - 1][j],
                                dp[i][j - 1] + grid[i][j] - grid[i][j - 1],
                                grid[i][j] - grid[i - 1][j],
                                grid[i][j] - grid[i][j - 1]});
                ans = max(ans,dp[i][j]);
            }
        }
        return ans;
    }
};